class Solution
{
public:
    long long subArrayRanges(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> lastNonLess(n);
        vector<int> nextGreater(n);
        vector<int> lastNonGreater(n);
        vector<int> nextLess(n);
        stack<int> sMin;
        stack<int> sMax;
        for (int i = 0; i < n; ++i)
        {
            while (!sMax.empty())
            {
                if (nums[sMax.top()] < nums[i])
                {
                    sMax.pop();
                }
                else
                {
                    break;
                }
            }
            if (sMax.empty())
            {
                lastNonLess[i] = -1;
            }
            else
            {
                lastNonLess[i] = sMax.top();
            }
            sMax.push(i);

            while (!sMin.empty())
            {
                if (nums[sMin.top()] > nums[i])
                {
                    sMin.pop();
                }
                else
                {
                    break;
                }
            }
            if (sMin.empty())
            {
                lastNonGreater[i] = -1;
            }
            else
            {
                lastNonGreater[i] = sMin.top();
            }
            sMin.push(i);
        }

        sMax = stack<int>();
        sMin = stack<int>();
        for (int i = n - 1; i >= 0; --i)
        {
            while (!sMax.empty())
            {
                if (nums[sMax.top()] <= nums[i])
                {
                    sMax.pop();
                }
                else
                {
                    break;
                }
            }
            if (sMax.empty())
            {
                nextGreater[i] = n;
            }
            else
            {
                nextGreater[i] = sMax.top();
            }
            sMax.push(i);

            while (!sMin.empty())
            {
                if (nums[sMin.top()] >= nums[i])
                {
                    sMin.pop();
                }
                else
                {
                    break;
                }
            }
            if (sMin.empty())
            {
                nextLess[i] = n;
            }
            else
            {
                nextLess[i] = sMin.top();
            }
            sMin.push(i);
        }

        long long result = 0;
        for (int i = 0; i < n; ++i)
        {
            long long num = nums[i];
            result += num * (i - lastNonLess[i]) * (nextGreater[i] - i);
            result -= num * (i - lastNonGreater[i]) * (nextLess[i] - i);
        }
        return result;
    }
};